// 给你一个字符串 s，找到 s 中最长的回文子串。

// 示例 1：
// 输入：s = "babad"
// 输出："bab"
// 解释："aba" 同样是符合题意的答案。

// 示例 2：
// 输入：s = "cbbd"
// 输出："bb"
/**
 * @param {string} s
 * @return {string}
 */
let longestPalindrome = function (s) {
    let len = s.length
    if (len < 2) return s
    let maxLen = 1
    let start = 0
    let dp = Array.from(new Array(len), () => new Array(len).fill(0))
    // 初始化：所有长度为 1 的子串都是回文串
    for (let i = 0; i < len; i++) {
        dp[i][i] = true
    }
    for (let L = 0; L <= len; L++) {
        for (let i = 0; i < len; i++) {
            let j = L + i - 1
            if (j >= len) {
                break
            }
            if (s[i] !== s[j]) {
                dp[i][j] = false
            } else {
                if (j - i < 3) {
                    dp[i][j] = true
                } else {
                    dp[i][j] = dp[i + 1][j - 1]
                }
            }

            if (dp[i][j] && j - i + 1 > maxLen) {
                maxLen = j - i + 1
                start = i
            }
        }
    }
    return s.substring(start, start + maxLen)
}
let s = 'acdbbdaa'
console.log(longestPalindrome(s))
